package 华为OD机试B卷复用题.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HJ4_找单词 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试B卷复用题/进阶题/input/4.txt"));
        MyUtil.START();
        Solution(in);
        MyUtil.END();
    }

    static String[][] matrix;
    static boolean[][] isVisited;
    static String word;
    static int N;
    static String res = "N";
    static StringBuilder tmpRes = new StringBuilder();

    // 力扣中等，单词搜索+记忆化路径，注意细节问题：1.有答案判断即可，频繁进入成功代码块有安全风险 2.单词长度和矩阵边长别搞混了。
    static void Solution(Scanner in) {
        N = in.nextInt();
        in.nextLine(); // 吸收回车
        matrix = new String[N][N];
        isVisited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            String[] sArray = in.nextLine().split(",");
            matrix[i] = sArray;
        }
        word = in.nextLine();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (matrix[i][j].equals(word.substring(0, 1))) {
                    tmpRes = new StringBuilder();
                    dfs(i, j, 0);
                }
            }
        }
        System.out.println(res);
    }

    static void dfs(int x, int y, int index) {

        if (!res.equals("N")) {
            return;
        }
        if (index == word.length()) {
            res = tmpRes.toString().substring(0, tmpRes.length() - 1);
            return;
        }
        if (x < 0 || x >= N || y < 0 || y >= N || isVisited[x][y]) {
            return;
        }
        if (matrix[x][y].equals(word.substring(index, index + 1))) {
            isVisited[x][y] = true;
            tmpRes.append(x).append(",").append(y).append(",");
            dfs(x - 1, y, index + 1); // 上
            dfs(x + 1, y, index + 1); // 下
            dfs(x, y - 1, index + 1); // 左
            dfs(x, y + 1, index + 1); // 右
            tmpRes.delete(tmpRes.length() - 4, tmpRes.length());
            isVisited[x][y] = false;
        }
    }
}
